時間複雜度(Time Complexity) 並非用來衡量演算法運行的絕對秒數,而是一種描述演算法執行時間隨問題規模 $n$ 增長而增長的數學函數。其基礎建立於「演算法分析是一種獨立於實作的演算法度量方法」這一核心原則之上。
為什麼它是通用語?
- 量化演進:大 O 記法忽略低階項與常數,僅聚焦於數量級(Order of Magnitude)。
- 度量的確定性:程式員通常以最壞情況(Worst Case) 作為基準,為效能提供下限保障。
- 跨環境決策:無論是在超級電腦還是嵌入式晶片中,從 $O(n^2)$ 優化至 $O(n \log n)$ 所帶來的效益都是本質性的。
計數法(Counting)
計算兩個字串中每個字元出現的次數。若字元計數列表相同,則兩個字串必為異序詞。此方法實現了 計數法:$O(n)$ 的高效性。